package algorithm.poj.p1000;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * 分析：
 * 1. 因为所有状态只有2^16=65536个，可以直接生成可能的所有状态。
 * 2. 将每一个状态用一个16bit的整数(short)保存，每次操作就是某些
 * 位上的数值和一个常数做取反操作(可以用异或实现)。
 * 
 * 
 * 实现：
 * 将每一个状态用一个16bit的整数保存，下面是格子和位的对应关系
 *  15 14 13 12
 *  11 10  9  8
 *   7  6  5  4
 *   3  2  1  0 
 * 如果一个格子是b则对应1，w对应是0。
 * 那么下面的输入，对应整数40344(0x1001_1101_1001_1000)：
 * bwwb
 * bbwb
 * bwwb
 * bwww
 * 
 * flip操作，等价于和下面的常数之一做异或：
 * 1100_1000_0000_0000	0xC800
 * 1110_0100_0000_0000	0xE400
 * 0111_0010_0000_0000	0x7200
 * 0011_0001_0000_0000	0x3100
 * 
 * 1000_1100_1000_0000	0x8C80
 * 0100_1110_0100_0000	0x4E40
 * 0010_0111_0010_0000	0x2720
 * 0001_0011_0001_0000	0x1310
 * 
 * 0000_1000_1100_1000	0x08C8
 * 0000_0100_1110_0100	0x04E4
 * 0000_0010_0111_0010	0x0272
 * 0000_0001_0011_0001	0x0131
 * 
 * 0000_0000_1000_1100	0x008C
 * 0000_0000_0100_1110	0x004E
 * 0000_0000_0010_0111	0x0027
 * 0000_0000_0001_0011	0x0013
 * 
 * 用一个s[65536]保存状态I到目标状态(0x1111_1111_1111_1111)的最少步数。
 * 那么，状态I到另一目标状态0x0000_0000_0000_0000的最少步数是s[J], 其中: 
 * J = I xor 0x1111_1111_1111_1111
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P1753 {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws Exception {

		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

        String input = ""; 
		if (false) {
	        String line;
	        
	        for (int i = 0; i < 4; i ++) {
	        	line = stdin.readLine();
	        	input += line.trim();
	        }
	        input = input.trim().replaceAll("b", "1").replaceAll("w", "0");
		} else {
			input = "1001110110011000";
		}
        
        String output = "";
        int r = flip(input);
        if (r == -1) {
        	output += "Impossible";
        } else {
            output += r; 
        }
        
        System.out.println(output);
	}
	
	private static int[] initialize() {
		
		//初始化状态数组
		int[] s = new int[65536];
		for (int i = 0; i < s.length; i ++) s[i] = -1;
		
		//初始化queue状态
		Queue q = new Queue(2048);
		q.put((int)0xFFFF);
		s[(int)0xFFFF] = 0;

		int ops[] = { 
				0xC800, 0xE400, 0x7200, 0x3100,
				0x8C80, 0x4E40, 0x2720, 0x1310,
				0x08C8, 0x04E4, 0x0272, 0x0131,
				0x008C, 0x004E, 0x0027, 0x0013
		};
		
		//start
		while (!q.isEmpty()) { 
			int n = q.get();
			for (int i = 0; i < ops.length; i ++) {
				int m = (int)(n^ops[i]);
				if (s[m] == -1) {
					s[m] = (int)(s[n]+1);
					q.put(m);
				}
			}
		}

		return s;
	}

	private static int flip(String input) {

		int n = Integer.valueOf(input, 2);
		int[] s = initialize();
		
		int c = 0, m = -1;
		for (int i = 0; i < s.length; i ++) {
			if (s[i] == -1) c ++;
			if (s[i] > m) m = s[i];
		}

		if (s[n] == -1) {
			return s[n^0xFFFF];
		} else if (s[n^0xFFFF] == -1) {
			return s[n];
		} else {
			return Math.min(s[n], s[n^0xFFFF]);
		}
	}
	

	private static class Queue {
		
		//用数组模拟一个Queue
		int q[];
		int start;
		int end;
		
		public Queue(int volumn) {
			
			this.q = new int[volumn];
			for (int i = 0; i < this.q.length; i ++) this.q[i] = -1;
			this.start = 0;
			this.end = 0;
		}
		
		public void put(int n) {
			
			int size = this.end-this.start;
			if (size < 0) {
				size += this.q.length;
			}
			if (size == this.q.length) {
				throw new RuntimeException("Queue is Full!");
			} else {
				this.q[this.end] = n;
				this.end = (this.end+1)%this.q.length;
			}
		}
		
		public int get() { 
			
			if (this.end == this.start) {
				throw new RuntimeException("Queue is Empty!");
			} else {
				int n = this.q[this.start];
				this.start = (this.start+1)%this.q.length;
				return n;
			}
		}
		
		public boolean isEmpty() {
			return this.end == this.start;
		}
	}

}
